import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 382. 链表随机节点
 * https://leetcode-cn.com/problems/linked-list-random-node/
 */
public class Solutions_382 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        ListNode head = MyLinkedListUtils.ArrayToListNode(arr);

        Solution obj = new Solution(head);
        int res1 = obj.getRandom();  // output: {1, 2, 3} 元素随机
        System.out.println(res1);
        int res2 = obj.getRandom();  // output: {1, 2, 3} 元素随机
        System.out.println(res2);
        int res3 = obj.getRandom();  // output: {1, 2, 3} 元素随机
        System.out.println(res3);
    }
}

/**
 * 解法二：一次遍历（添加到 list 列表后，根据索引取随机数）（12ms）
 */
class Solution {
    private List<Integer> list = null;

    /** @param head The linked list's head.
    Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
        ListNode cur = head;
        list = new ArrayList<>();
        while (cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
    }

    /** Returns a random node's value. */
    public int getRandom() {
        // 获取随机索引，索引范围：[0, list.size() - 1]
        int idx = (int)(Math.random() * list.size());
        return list.get(idx);
    }
}

/**
 * 解法一：一次遍历（遍历过程中选择随机结果）（14ms）
 */
class Solution2 {
    private ListNode head = null;
    private Random random = null;

    /** @param head The linked list's head.
    Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution2(ListNode head) {
        this.head = head;
        random = new Random();
    }

    /** Returns a random node's value. */
    public int getRandom() {
        if (head == null) {
            return -1;
        }
        // 初始结果为链表的头结点（若是链表中只有一个结点，那么 getRandom 的结果总是 head.val）
        int res = head.val;
        ListNode next = head.next;
        int i = 2;
        // 迭代链表
        while (next != null) {
            // 判断条件，可灵活设置
            if (random.nextInt(i) == 0) {
                res = next.val;
            }
            // i 表示结点的个数 + 1，即表示可以选择的结点为 [0, i - 1]
            i ++;
            next = next.next;
        }
        return res;
    }
}

